home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 051-075 / scopedisk57 / expand / expand.c < prev    next >
C/C++ Source or Header  |  1995-03-19  |  5KB  |  153 lines
  1. /*                          E X P A N D . C 
  2.  *
  3.  *  A file maintenance filter utility to EXPAND files compressed by the
  4.  *  public domain COMPRESS v4.0 utility by Spencer W. Thomas, et al.
  5.  *
  6.  *  Algorithm from "A Technique for High Performance Data Compression",
  7.  *  Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  8.  *
  9.  *  The impetus for this program comes from a desire to EXPAND files
  10.  *  in an MS-DOS environment which have been COMPRESSed with 16 bit
  11.  *  codes in UNIX(tm) or other environments.  Memory usage for this
  12.  *  program is less than 250 kbytes for the full 16 bit case.
  13.  *  The code uses many ANSI-C style contructs with no apologies.
  14.  *-----------------------------------------------------------------------
  15.  *  Author: Lyle V. Rains
  16.  *      Based on the sources of COMPRESS.C v4.0 by Spencer Thomas, et al.
  17.  *-----------------------------------------------------------------------
  18.  *  Revision History:
  19.  */
  20.  
  21. #define EXPAND
  22. #include "expand.h"
  23.  
  24. CONST int Maxbits = MAXBITS;
  25.  
  26. static char FAR * sfx = NULLPTR(char);
  27.  
  28. #if (SPLIT_PFX)
  29.   static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
  30. #else
  31.   static CODE FAR *pfx = NULLPTR(CODE);
  32. #endif
  33.  
  34.  
  35. static int alloc_tables(maxcode)
  36.   CODE maxcode;
  37. {
  38.   static CODE oldmaxcode = 0;
  39.    if (maxcode > oldmaxcode) {
  40. #   if (SPLIT_PFX)
  41.       free_array(CODE, pfx[1], 128);
  42.       free_array(CODE, pfx[0], 128);
  43. #   else
  44.       free_array(CODE, pfx, 256);
  45. #   endif
  46.     free_array(char, sfx, 256);
  47.     if (   alloc_array(char, sfx, maxcode + 1, 256)
  48. #     if (SPLIT_PFX)
  49.         || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
  50.         || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
  51. #     else
  52.         || alloc_array(CODE, pfx, maxcode + 1, 256)
  53. #     endif
  54.       )
  55.     {
  56.       oldmaxcode = 0;
  57.       return (NOMEM);
  58.     }
  59.     oldmaxcode = maxcode;
  60.   }
  61.   DBG(("   sfx = 0x%lx\n", (long)sfx));
  62. # if (SPLIT_PFX)
  63.     DBG(("   pfx = {0x%lx,  0x%lx}\n", (long)pfx[0], (long)pfx[1]));
  64. # else
  65.     DBG(("   pfx = 0x%lx\n", (long)pfx));
  66. # endif
  67.   return (OK);
  68. }
  69.  
  70.  
  71.  
  72. int expand(in, out, maxbits, clearmode)
  73.   FILE *in;
  74.   FILE *out;
  75.   int maxbits;
  76.   int clearmode;
  77. {
  78.   register int i;
  79.   unsigned int bits;
  80.   char sufxchar;
  81.   register CODE code;
  82.   CODE prefxcode, savecode;
  83.   CODE nextfree, highcode, maxcode;
  84.   int fulltable, cleartable;
  85.   static char token[MAXTOKLEN];         /* String buffer to build token */
  86.   static CODE tablesize = 0;
  87.  
  88.   
  89.   alloc_tables(maxcode = ~(~(CODE)0 << maxbits));
  90.   cleartable = YES;
  91.   savecode = CLEAR;
  92.   do {
  93.     if ((code = savecode) == CLEAR && cleartable) {
  94.       highcode = ~(~(CODE)0 << (bits = INITBITS));
  95.       fulltable = NO;
  96.       nextfree = (cleartable = clearmode) == NO ? 256 : FIRSTFREE;
  97.       DBG(("table cleared\n"));
  98.       if (!nextcode(in, &prefxcode, bits, highcode)) break;
  99.       putc((sufxchar = (char)prefxcode), out);
  100.       continue;
  101.     }
  102.     i = 0;
  103.     if (code >= nextfree && !fulltable) {
  104.       if (code != nextfree) return (CODEBAD);     /* Non-existant code */
  105.       /* Special case for sequence KwKwK (see text of article)         */
  106.       code = prefxcode;
  107.       token[i++] = sufxchar;
  108.     }
  109.     /* Build the token string in reverse order by chasing down through
  110.      * successive prefix tokens of the current token.  Then output it.
  111.      */
  112.     while (code >= 256) {
  113. #     ifndef NDEBUG
  114.         /* These are checks to ease paranoia. Prefix codes must decrease
  115.          * monotonically, otherwise we must have corrupt tables.  We can
  116.          * also check that we haven't overrun the token buffer.
  117.          */
  118.         if (code <= prefix(code)) return (TABLEBAD);
  119.         if (i >= MAXTOKLEN) return (TOKTOOBIG);
  120. #     endif
  121.       token[i++] = suffix(code);
  122.       code = prefix(code);
  123.     }
  124.     putc(sufxchar = (char)code, out);
  125.     while (--i >= 0) putc(token[i], out);
  126.     if (ferror(out)) return (WRITEERR);
  127.     /* If table isn't full, add new token code to the table with
  128.      * prefxcode and sufxchar, and remember current code.
  129.      */
  130.     if (!fulltable) {
  131.       code = nextfree;
  132.       assert(256 <= code && code <= maxcode);
  133.       prefix(code) = prefxcode;
  134.       suffix(code) = sufxchar;
  135.       prefxcode = savecode;
  136.       if (code++ == highcode) {
  137.         if (highcode >= maxcode) {
  138.           DBG(("table full\n"));
  139.           fulltable = YES;
  140.           --code;
  141.         }
  142.         else {
  143.           ++bits;
  144.           highcode += code;        /* code == highcode + 1 */
  145.         }
  146.       }
  147.       nextfree = code;
  148.     }
  149.   } while (nextcode(in, &savecode, bits, highcode));
  150.   return (ferror(in) ? READERR : OK);
  151. }
  152.  
  153.